package com.clstu.stack;

/**
 * 利用栈结构实现一个计算器,可以计算普通的 + - * / 算式
 * 只能做一位数的运算 -----(改进)-------> 可以做多位数的运算-----(思考:改进2)------->实现带括号和空格的表达式的计算
 */
public class Calculator {
    public static void main(String[] args) {
        //在主方法中完成对表达式的判断
        String expression = "3+60*2-5*20";
        //定义数栈和符号栈
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operaStack = new ArrayStack2(10);
        //思路分析,依次扫描这个表达式,
        // 1.如果是数字,就入数栈,
        // 2.如果是符号,符号栈为空是直接入栈,如果符号栈不空,就跟栈顶符号比较,优先级更高就可以入栈
        //  优先级栈比顶符号小就 弹出一个符号和两个数据 让他们做运算,结果存入数栈,再将被扫描的符号入栈
        // 3.如果扫描到了结尾,就循环 弹出一个符号和两个数据 让他们做运算,结果存入数栈,直到符号栈空
        //定义相关辅助变量
        int n1 = 0;//操作数1
        int n2 = 0;//操作数2
        char op = ' ';//存放操作符
        char ch = ' ' ;//存放扫描到的符号
        int index = 0;//用于扫描
        int res = 0;//保存运算结果
        String num = "";//用于拼接保存多位数
        //循环扫描
        while (true){
            //如果表达式扫描完
            if(index == expression.length()){
                break;
            }
            //取出索引为index的字符
            ch = expression.substring(index,index+1).charAt(0);
            //判断是操作符还是数字
            if(isOpera(ch)){
                //判断是否符号栈空
                if(operaStack.isEmpty()){
                    operaStack.push(ch);
                }else {
                    //跟栈顶指针比较优先级
                    if(priority(ch) <= priority((char) operaStack.peek())){//优先级小的话
                        //弹出两个数和一个符号做运算
                        //先接收n2在接收n1,因为后进先出
                        n2 = numStack.pop();
                        n1 = numStack.pop();
                        op = (char) operaStack.pop();
                        res = cal(n1,n2,op);
                        //结果入数栈,符号入符号栈
                        numStack.push(res);
                        operaStack.push(ch);
                    }else {//优先级大的话
                        operaStack.push(ch);
                    }
                }
            }else {//如果ch是数字
                //保存数字
                num = num+String.valueOf(ch);
                //如果扫描到了结尾,直接压栈退出
                if(index == expression.length()-1){
                    numStack.push(Integer.parseInt(num));
                    break;
                }
                //如果扫描的下一位不再是数字则压栈,否则等数字读完了再压栈
                if(isOpera(expression.substring(index+1,index+2).charAt(0))) {
                    numStack.push(Integer.parseInt(num));
                    //num清空
                    num="";
                }
            }
            //索引++
            index++;
        }
        //扫描完后再循环计算,直到符号栈空或者数据栈中只有一个数据
        while (true){
            //如果遍历完
            if(operaStack.isEmpty()){
                break;
            }
            n2 = numStack.pop();
            n1 = numStack.pop();
            op = (char) operaStack.pop();
            res = cal(n1, n2, op);
            numStack.push(res);
        }
        //输出结果
        System.out.println(expression+" = "+numStack.pop());
    }

    //编写方法判断操作符的优先级,返回数字越大优先级越高
    public static int priority(char c){
        if(c=='+'||c=='-'){
            return 1;
        }else if(c=='*'||c=='/'){
            return 2;
        }else {
            //如果是其他符号
            throw new RuntimeException("该符号暂时不能用来做运算");
        }
    }

    //编写方法判断是否是运算符
    public static boolean isOpera(char c){
        return c=='+'||c=='-'||c=='*'||c=='/';
    }

    //编写方法用于运算
    public static int cal(int n1,int n2,char c){
        switch (c){
            case '+':
                return n1+n2;
            case '-':
                return n1-n2;
            case '*':
                return n1*n2;
            case '/':
                return n1/n2;
            default:
                throw new RuntimeException("运算符暂时不能做计算,运算失败");
        }
    }

}
/**
 * 数组实现栈结构
 */
class ArrayStack2{
    private int maxSize;//最大占空间
    private int[] arr;//数组,用于保存数据
    private int top;//指向栈顶,-1表示空

    //构造器
    public ArrayStack2(int maxSize){
        this.maxSize = maxSize;
        arr = new int[maxSize];
        top = -1;
    }

    //是否栈空
    public boolean isEmpty(){
        return top==-1;
    }

    //是否栈满
    public boolean isFull(){
        return top == maxSize-1;
    }

    //压栈
    public void push(int data){
        //先判断是否栈满
        if(isFull()){
            System.out.println("栈满,压栈失败");
            return;
        }
        //压栈
        top++;
        arr[top] = data;
    }

    //出栈
    public int pop(){
        //先判断是否栈空
        if(isEmpty()){
            throw new RuntimeException("栈空,出栈失败");//抛出异常就会退出方法,无需再return,
        }
        //出栈
        int val = arr[top];
        top--;
        return val;
    }

    //编写方法显示栈中的所有数据
    public void look(){
        //如果栈空
        if(isEmpty()){
            System.out.println("栈空,没有数据");
            return;
        }
        //遍历打印
        for (int i = top; i >= 0; i--) {
            System.out.printf("arr[%d] = %d \n",i,arr[i]);
        }
    }

    //编写方法查看栈顶数据,只查看,不出栈
    public int peek(){
        //是否栈空
        if(isEmpty()){
            throw new RuntimeException("栈空,查看栈顶失败");
        }
        return arr[top];
    }



}